class Solution(object):
    def bstFromPreorder(self, preorder):
        """
        :type preorder: List[int]
        :rtype: TreeNode
        """

        def bst(preorder, l, h):
            if l > h:
                return None
            if l == h:
                return TreeNode(preorder[l])
            
            root = TreeNode(preorder[l])
            #创建左子树, preorder中小于root的部分 
            cur = l
            while cur <= h and preorder[cur] <= preorder[l]:
                cur += 1

            root.left = bst(preorder, l + 1, cur - 1)
            root.right = bst(preorder, cur, h)
            return root

        return bst(preorder, 0, len(preorder) - 1)
